package 剑指Offer.medium;

import java.math.BigInteger;
import java.util.Arrays;

public class 剪绳子2 {
    class Solution {
        public int cuttingRope(int n) {
            BigInteger[] dp = new BigInteger[n + 1];
            Arrays.fill(dp, BigInteger.valueOf(1));//填充空值
            dp[2] = BigInteger.valueOf(1);//初始化
            for (int i = 3; i < n + 1; i++) {
                //对某一确定长度的绳子，找到两分的最大值；每段都两分，宏观上就是m分
                for (int j = 2; j < i; j++) {
                    //找到当前规划最大值，与曾经规划做比较
                    BigInteger temp = BigInteger.valueOf(j * (i - j)).max(dp[i - j].multiply(BigInteger.valueOf(j)));
                    dp[i] = temp.compareTo(dp[i]) > 0 ? temp : dp[i];
                }
            }
            return dp[n].mod(BigInteger.valueOf(1000000007)).intValue();
        }
    }
}
